1. Field of the Invention
The present invention relates to circuits that perform arithmetic operations. More specifically, the present invention relates to a method and an apparatus that efficiently performs error-check and exact-check operations for Newton-Raphson divide and square-root operations.
2. Related Art
Several techniques can be used to perform divide, a/b, and square-root, √{square root over (b)}, operations. One popular technique is to use the Newton (sometimes called the Newton-Raphson) method. As typically implemented for the division operation, the Newton-Raphson method first finds an approximation to a zero of the function
      f    ⁡          (      x      )        =      1    -          1      bx      for the reciprocal of the denominator, 1/b. Similarly, for the square-root operation, the Newton-Raphson method first finds an approximation to a zero of the function
      f    ⁡          (      x      )        =      1    -          1              bx        2            for the reciprocal of the square root, 1/√{square root over (b)}.
The Newton-Raphson method starts with an initial estimate, e, of the zero to the function. Better estimates are obtained by iterating using the formula
      e    next    =      e    -                  f        ⁡                  (          e          )                                      f          ′                ⁡                  (          e          )                    This computation can be accomplished with only the following operations: add, subtract, multiply, and, divide-by-two (for square root, which can be accomplished with a shift). To simplify the method, the denominator, b, (for divide) is normalized to be between one half and one, and the value, b, (to find the square root of) is normalized to be between ¼ and one. Thus, the zero of the function (for both cases) is between one and two. A property of the Newton-Raphson method that may be maintained when used with these functions is that, independent of the initial estimate e, all succeeding estimates are less than the zero of the function.
Sufficient Newton-Raphson iterations are carried out to obtain the desired internal accuracy. Then a multiplication is performed. For divide, the result of the Newton-Raphson iterations is multiplied by the numerator, a, to obtain an internal result, m. For square root, the result of the Newton-Raphson iterations is multiplied by b (because b * 1/√{square root over (b)}=√{square root over (b)}) to obtain an internal result m. In both cases, m is an approximation to the exact result, r. Also, the internal result, m, needs to have more accuracy than the accuracy of the final result for the method described below. Furthermore, we ensure that m is less than the exact result. The internal result, m, is also called the “result of the Newton-Raphson method”.
The result of the Newton-Raphson method contains only a finite amount of accuracy. Thus, it is not exact. The desired result is the exact result rounded according to one of the following three rounding modes: (1) round towards zero (truncate), (2) round towards infinity (round up), or (2) round to nearest (if exactly half way between representable results, round to “even” to make the least-significant bit (LSB) zero).
The internal estimate, m, is rounded to produce a rounded result, t, which functions as a proposed answer. However, no matter how much extra accuracy has been achieved, the extra accuracy is finite, so the value of t may not be the same as the rounded exact result. For example, consider FIG. 1 which illustrates a segment of the real number line, with vertical lines representing values that can be represented with the finite external accuracy. Note that in the expression t+1, the “+1” represents 1 added to the least-significant bit of t (with external accuracy).
The internal value, m, is the current (best obtained) estimate. The example which appears in FIG. 1 is for rounding towards zero (down), so that m is truncated to t. However, the exact result is the value r. This means that no matter how much accuracy is obtained in computing, m, it is always possible that a representable value (in FIG. 1, the value is t+1) is between m and r. In order to produce the correct result, this situation must be evaluated and t must be replaced with t+1 if appropriate.
A computation may be performed to determine when the proposed result is different from the desired result. Let t+1 be the proposed result plus one in the least significant bit position of the result precision, and t+½ be the proposed result plus one half in the least significant bit position of the result precision.    Divide a/b, round down—Compute g=((t+1)*b)−a. If g>0, the desired answer is t, otherwise the desired answer is t+1. If g=0 the answer (t+1) is exact.    Divide a/b, round nearest—Compute g=((t+½)*b)−a. If g>0, the desired answer is t. If g<0, the desired answer is t+1. If g=0 and the least-significant bit of t is on, the desired answer is t+1. If g=0 and the least-significant bit of t is off, the desired answer is t. If (t*b)−a =0, the answer (t) is exact.    Divide a/b, round up—Compute g=(t*b)−a. If g<0, the desired answer is t+1, otherwise the desired answer is t. If g=0 the answer (t) is exact.    Square root of b, round down—Compute g=((t+1)*(t+1))−b. If g>0, the desired answer is t, otherwise the desired answer is t+1. If g=0, the answer (t+1) is exact.    Square root of b, round nearest—Compute g=((t+½)*(t+½))−b. If g>0, the desired answer is t. If g<0, the desired answer is t+1. In this case, g is never equal to zero. If the desired answer (t) squared is equal to b, the answer is exact.    Square root of b, round up—Compute g=(t*t)−b. If g<0, the desired answer is t+1, otherwise the desired answer is t. If g=0 the answer (t) is exact.
Note that for rounding up and rounding down, one computation determines both what the correct answer is and if that answer is exact. However, for the most commonly-used mode, rounding-to-nearest, two computations are required to find both what the correct answer is and if it is exact or not. (Alternatively, one computation may be used to determine if the result is a correct result, and a comparison can be used to determine if the correct result is exact.)
Hence, what is needed is a method and an apparatus for more-efficiently performing the above-described error-check and exact-check computations.